package org.example;

public class Test3 {
    //leetcode 面试题 02.07 链表相交 https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
    public int getListLength(ListNode head) {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1 = getListLength(headA), len2 = getListLength(headB);
        //为了方便，保证headA永远是长的一个链表
        if (len2 > len1) {
            ListNode tmp = headA;
            headA = headB;
            headB = tmp;
        }
        int gap = Math.abs(len1-len2);
        ListNode cur1 = headA, cur2 = headB;
        while (cur1 != null && gap > 0) {
            cur1 = cur1.next;
            gap--;
        }
        while (cur1 != null && cur2 != null) {
            if (cur1 == cur2) return cur1;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return null;
    }
}
